Typically with many bus systems, a device wishing to initiate a transfer between itself and another device must request and be granted the exclusive use of the bus for a period of time. Since more than one device may request the bus at the same time, an arbiter is necessary to determine which requester will be granted immediate use of the bus and which requesters must wait.
In some previous systems employing agents, any agent wishing to use the bus places a request signal to the arbiter. If two or more agents are requesting the bus at the same time, the arbiter chooses one of those requesters by sending a grant signal to that requester. In other previous systems, the processor bus has distributed arbitration. All agents know in advance which agent has priority, and that agent seizes it. When a requesting agent makes a request, the target device (the device with which the requesting agent wishes to communicate data) may not be able to accept that particular transaction. If not, the requesting agent receives a retry indication from the target and must relinquish the bus. The requesting agent re-issues the request usually by sending another request signal to the arbiter to start the cycle all over again. In this situation, the target device is receiving the transaction from the agent, but the target device is not satisfying the request.
The retry response indicates to the requesting agent that the transaction could not be completed at the present time. Further, the cycle to request use of the target device should be retried at a later time, if required for the progress of the requesting processor. The arbitration mechanism employed, such as round robin, hierarchical, etc, attempts to allocate use of the target device by all of the agents attempting to use the target device.
In systems that share a system resource, instruction starvation may occur. In general, instruction starvation occurs when one requesting agent repeatedly attempts to make forward progress on executing an instruction stream but for some reason is repeatably prevented from making any forward progress on executing that instruction stream.
For example, if agent A requests and is granted the bus, then agent A can transfer enough data to fill up a buffer before terminating the transaction. If agent B is then granted the bus while the buffer is still full, agent B receives a retry response and must drop the request. As the next requesting device in the rotation, agent A may request and be granted the bus again. The buffer has by then had time to free up some memory space, which agent A proceeds to fill up again. In time, agent B gets another chance to have access to the bus and request use of the buffer, but agent B again receives a retry response, since the buffer is by now full again. In this manner, agent A will be granted access every time it makes a bus request, while agent B will never be granted access until device A has completed all transfers. This defeats the purpose of rotating priority, which is to give every device equal access to the bus and use of a target device. Worse yet, agent B may be indefinitely starved.
A transaction issued from an agent in a multiple agent system is typically composed of several parts such as the agent identifier (agent ID), transaction identifier (transaction ID), and the transaction type. The agent ID uniquely identifies which agent i.e. device or thread sent the transaction. An agent also assigns a unique transaction ID to each transaction issued in order to monitor the progress of that transaction. For example, the agent may issue ten transactions prior to receiving a completion back to the first issued transaction. Thus, the agent keeps track of when completion has been received based on what transaction ID's have been received back. In this way, the agent is able to determine what has occurred and what still needs to happen next for a particular transaction by use of the transaction identifier. Also, the agent is able to associate completions with the correct transaction. The transaction type communicates the specific kind of transaction included in this transaction, such as an input-output read operation, an input-output write operation, bus line request, a cache eviction, etc.
A prior art technology attempted to detect instruction starvation by associating retry responses with transactions through their transaction ID). Thus, this previous instruction starvation technology depended on agents re-issuing the exact same transaction ID to the same target. Unfortunately, some processors issue speculative transactions that are not issued again once the retry response is received. Thus, if a speculative transaction triggered activation of the instruction starvation resolution mechanism and then never issued that speculative transaction again, the computer system could eventually hang. The computer system could hang because the mechanism to resolve instruction starvation activates and then waits for reissuance of this speculative transaction with its unique transaction ID that will never be issued again.
While the invention is subject to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and will herein be described in detail. The invention should be understood to not be limited to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention.